package com.my.collection.graph.v6;

import com.my.collection.graph.v1.ElementExistException;
import com.my.collection.graph.v1.ElementNotFoundException;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created by ZhongGang
 * at 2018/10/25 17:22
 * <p>
 * 无向加权图，基于邻接矩阵
 */
public class Graph<V> {
    private Map<V, Integer> vertexes = new HashMap<>();//顶点与矩阵下标对应关系集合
    private int[][] edges = new int[][]{};//顶点与顶点间的连接关系矩阵
    private int size;//顶点个数

    public void addVertex(V v) {
        if (this.vertexes.containsKey(v)) {
            throw new ElementExistException();
        }

        this.vertexes.put(v, this.size++);
        int[][] copyEdges = new int[this.size][this.size];
        for (int i = 0; i < copyEdges.length; i++) {
            if (i >= this.edges.length) {
                copyEdges[i] = new int[this.size];
            } else {
                int[] newEdges = Arrays.copyOf(this.edges[i], this.size);
                copyEdges[i] = newEdges;
            }
        }
        this.edges = copyEdges;
    }

    public void addEdge(V from, V to) {
        addEdge(from, to, 1);
    }

    public void addEdge(V from, V to, int weight) {
        if (!this.vertexes.containsKey(from) || !this.vertexes.containsKey(to)) {
            throw new ElementNotFoundException();
        }

        Integer row = this.vertexes.get(from);
        Integer column = this.vertexes.get(to);
        this.edges[row][column] = weight;
        this.edges[column][row] = weight;
    }

    @Override
    public String toString() {
        String[] edgesToStr = new String[this.size];
        for (int i = 0; i < this.edges.length; i++) {
            edgesToStr[i] = Arrays.toString(this.edges[i]);
        }

        return "Graph{" +
                "vertexes=" + vertexes +
                ", edges=" + Arrays.toString(edgesToStr) +
                ", size=" + size +
                '}';
    }
}
